//
// Created by Administrator on 2021/11/16.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>> &mat) {
        // 某一行的最大值，如果比上下行的最大值都大，则是一个顶峰
        //----二分找row号+遍历col 找最大
        int Row = (int) mat.size();
        int Col = (int) mat[0].size();
        int up = 0;
        int down = Row - 1;
        while (up <= down) {
            int mid = (up + down) / 2;
            int up_neighbor_max = 0 <= mid - 1 ? *max_element(mat[mid - 1].begin(), mat[mid - 1].end()) : -1;
            int cur_max = *max_element(mat[mid].begin(), mat[mid].end());
            int cur_max_i = max_element(mat[mid].begin(), mat[mid].end()) - mat[mid].begin();
            int down_neighbor_max = mid + 1 < Row ? *max_element(mat[mid + 1].begin(), mat[mid + 1].end()) : -1;
            // 比相邻行的最大值都大，则符合要求
            if (cur_max >= max(up_neighbor_max, down_neighbor_max)) {
                return vector<int>{mid, cur_max_i};
            } else if (up_neighbor_max >= max(cur_max, down_neighbor_max)) { // 上面大
                down = mid;
            } else { // 下面大
                up = mid + 1;
            }
        }
        return vector<int>{};
    }
};

int main() {
    vector<vector<int>> mat{{10, 20, 15},
                            {21, 30, 14},
                            {7,  16, 32}};
    Solution solution;
    vector<int> ans = solution.findPeakGrid(mat);
    for (const int &x:ans) cout << x << endl;
    return 0;
}


